/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        295c.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/18 9:36
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
#include "../header.h"

class MedianFinder {
    multiset<int> data;
    multiset<int>::iterator mid;
public:
    /** initialize your data structure here. */
    MedianFinder() : mid(data.end()) {}

    void addNum(int num) {
        const int n = data.size();
        data.insert(num);
        if (n == 0)
            mid = data.begin();
        else if (num < *mid)
            mid = (n & 1) ? mid : prev(mid);
        else
            mid = (n & 1) ? next(mid) : mid;
    }

    double findMedian() {
        const int n = data.size();
        return (*mid + *next(mid, n % 2 - 1)) * 0.5;
    }
};
